#pragma once

#include <iostream>

using namespace std;

/*整数1到n从小到大依次进栈，期间可以出栈。设计算法判定给定的1到n的整数序列是否是正确的出栈序列，如果是返回true，如果不是返回false*/
class StackOutSeries {
public:
	
	bool judge(int a[], int n) {
		//新建一个堆栈用于存储从1到n的序列
		int stack[5];
		int top = -1;//栈顶指针
		int k = 0; //待检测数组的索引
		int c = 0; //入栈数字

		while (c <= n && k != n) {//若全部数据没有全部入过栈则继续
			if (top == -1) {//如果是空栈则下一步肯定是插入数据
				if (c + 1 > n) break;
				stack[++top] = ++c;
			}
			if (stack[top] != a[k]) {//栈顶数据不等于检测数组的字符说明没有出栈操作，则继续入栈下一个数据
				if (c + 1 > n) break;
				stack[++top] = ++c;
			}else {//栈顶数据等于待检测数字，说明有出栈，此时应当弹出栈顶数据，并将检测序号加1
				--top;
				++k;
			}
		}
		//如果符合入栈出栈顺序,则最终栈为空，并且待检测数组序号为n
		if (top == -1 && k == n) {
			return true;
		}
		else {
			return false;
		}
	}
};